package com.solution.stack;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public String decodeString(String s) {
        Deque<String> stk = new LinkedList<>();
        Deque<Integer> mul = new LinkedList<>();
        int multi = 0;
        StringBuffer res = new StringBuffer();
        for ( char ch : s.toCharArray() ) {
            // if ( Character.isDigit(ch) ) {  // 数字
            if ( ch >= '0' && ch <= '9' ) {  // 数字
                multi = multi * 10 + Integer.valueOf(ch + "");
            } else if ( ch == '[' ) {  // 将左括号之前的数据存起来
                stk.push(res.toString());
                mul.push(multi);
                res.setLength(0);
                multi = 0;
            } else if ( ch == ']' ) {  // 将左括号右边的元素复制cur_multi倍，再与左括号左边（即之前的）字符拼接
                StringBuilder tmp = new StringBuilder();
                int cur_multi = mul.pop();
                while ( cur_multi > 0 ) {
                    tmp.append(res);
                    cur_multi--;
                }
                tmp.insert(0, stk.pop());
                res = new StringBuffer( tmp );
            }else {  // 字母 (letter)
                res.append(ch);
            }
        }
        return res.toString();
    }
}
